package com.leecode;

import com.test.TreeNode;

import java.util.Arrays;

/**
 * 根据一棵树的前序遍历与中序遍历构造二叉树。
 * <p>
 * 注意:
 * 你可以假设树中没有重复的元素。
 * <p>
 * 例如，给出
 * <p>
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 *   3
 *  / \
 * 9  20
 *   /  \
 *  15   7
 */
public class Leet105 {
	public static void main(String[] args) {
		new Leet105().buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
	}

	public TreeNode buildTree(int[] pre, int[] in) {

		return null;
	}

	//12%,0%
	public TreeNode buildTree2(int[] pre, int[] in) {
		if (pre.length == 0 || in.length == 0) return null;

		TreeNode root = new TreeNode(pre[0]);
//		int rootIndexIn = Arrays.binarySearch(in, pre[0]);//用这方法前必调sort(),root元素在in中的index
		int rootIndexIn = getIndex(in, pre[0]);
		if (rootIndexIn != 0) {
			int[] leftPre = Arrays.copyOfRange(pre, 1, 1 + rootIndexIn);
			int[] leftIn = Arrays.copyOf(in, rootIndexIn);
			root.left = buildTree(leftPre, leftIn);
		}
		if (rootIndexIn != in.length - 1) {
			int[] rightPre = Arrays.copyOfRange(pre, 1 + rootIndexIn, pre.length);
			int[] rightIn = Arrays.copyOfRange(in, rootIndexIn + 1, in.length);
			root.right = buildTree(rightPre, rightIn);
		}

		return root;
	}

	public int getIndex(int[] arr,int target){
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == target) {
				return i;
			}
		}
		return -1;
	}

}
